Ottimizzazioneè il processo matematico di trovare la "migliore" soluzione—minimizzando o massimizzando una funzione obiettivo—entro una regione ammissibile definita, soggetta a regole specifiche.
Metodi classici vs. metodi intelligenti
- Metodo di Newton-Raphson:Un approccio iterativo per trovare radici che utilizza derivate di secondo ordine (matrice hessiana).
- Discesa del gradiente:Un metodo del primo ordine che si muove verso il minimo locale seguendo il gradiente negativo.
- Algoritmi evolutivi (EAs):Metodi di ricerca stocastici basati su popolazioni, ispirati alla selezione naturale biologica.
Concetti fondamentali
È fondamentale distinguere tra il Vettore delle decisioni (le variabili che modificiamo) e il Funzione obiettivo (il criterio di successo).
Insidie dell'encoding
Fai attenzione al Gradiente che svanisce nei metodi basati sul calcolo differenziale e al Dirupi di Hamming negli algoritmi evolutivi con codifica binaria. Un semplice incremento decimale (ad esempio da 7 a 8) può richiedere l'inversione di tutti i bit (da 0111 a 1000), creando un "dirupo" che ostacola l'efficienza della ricerca. Usa il Codifica di Gray per mitigarne gli effetti.
Implementazione in Python: Discesa del gradiente
Domanda 1
Perché un problema di ottimizzazione convessa è considerato "più facile" di uno non convesso?
Domanda 2
Nel contesto degli Algoritmi Evolutivi, cosa rappresenta il "fenotipo"?
Studio di caso: Massimizzare l'area di un triangolo
Leggi lo scenario riportato di seguito e rispondi alle domande di formulazione.
Considera il problema di massimizzare l'area di un triangolo rettangolo in cui la lunghezza dell'ipotenusa $c$ è fissata.
Q
1. Identifica le variabili di decisione e la funzione obiettivo.
Risposta:
Variabili: Le lunghezze dei due cateti, $a$ e $b$.
Funzione obiettivo: Massimizza $Area = \frac{1}{2} \cdot a \cdot b$.
Variabili: Le lunghezze dei due cateti, $a$ e $b$.
Funzione obiettivo: Massimizza $Area = \frac{1}{2} \cdot a \cdot b$.
Q
2. Enuncia il vincolo basato sulle proprietà geometriche.
Risposta:
Basato sul teorema di Pitagora, il vincolo è: $a^2 + b^2 = c^2$.
Basato sul teorema di Pitagora, il vincolo è: $a^2 + b^2 = c^2$.
Q
3. Se si utilizza il metodo di Newton-Raphson, quale matrice deve essere calcolata per tenere conto delle derivate parziali di secondo ordine?
Risposta:
La Matrice hessiana ($H$), che contiene tutte le derivate parziali di secondo ordine della funzione obiettivo.
La Matrice hessiana ($H$), che contiene tutte le derivate parziali di secondo ordine della funzione obiettivo.